313D - Ilya and Roads - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

// Template (v1.3.3 - 2023-02-05) (codeforces:cebolinha, atcoder:edu) {{{

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#define int long long
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr)

template<class T> using V = vector<T>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using ll = long long;

#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define sz(x) (int) (x).size()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define nemo ><>
#define loop(ii, n) for (int ii = 0; ii < (n); ii++)
#define xloop(ii, l, r) for (int ii = (l); ii <= (r); ii++)
#define cond(c, t, f) ((c) ? (t) : (f))
#define mem(a, b) memset((a), (b), sizeof(a))
#define inbounds(x, l, r) ((l) <= (x) && (x) <= (r))
#define L1(res...) [&](auto x){ return res; }
#define L2(res...) [&](auto x, auto y){ return res; }

#define mp make_pair
#define mt make_tuple

template<class T, class U> inline void miq(T& a, U b){if (a > b) a = b;}
template<class T, class U> inline void maq(T& a, U b){if (a < b) a = b;}

template<class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.ff >> p.ss; return is; }
template<class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &a : v) is >> a; return is; }
template<class T, class U> ostream &operator<<(ostream &os, pair<T, U> const& p) { os << "(" << p.first << " " << p.second << ")"; return os; }
template<class T> ostream &operator<<(ostream &os, vector<T> const& v) { for (int i = 0; i < v.size(); i++) os << cond(i," ","") << v[i]; return os; }
template<class T, class U> ostream &operator<<(ostream &os, map<T, U> const& m) { bool first = true; for (auto const& [k, v] : m) { if (!first) os << " "; first = false; os << "{" << k << " : " << v << "}"; } return os; }
template<class T> ostream &operator<<(ostream &os, set<T> const& s) { for (auto it = s.begin(); it != s.end(); it++) os << cond(it != s.begin()," ","") << *it; return os; }

template<class... A> void in(A &...a) { ((cin >> a), ...); }
template<class... A> void out(A const&... a) { ((cout << a << " "), ...); cout << endl; }
template<class... A> void print(A const&... a) { ((cout << a), ...); }
#define var(x) "[", #x, " ", x, "] "
template<class... A> void db(A const&... a) { ((cout << (a)), ...); cout << endl; }
//}}}

const int INF = 0x3f3f3f3f3f3f3f3f;

signed main(){
    fastio;
    int n, m, k; cin >> n >> m >> k;
    V<V<int>> v(n+1, V<int>(n+1, INF));
    loop(i, m){
        int l, r, c; cin >> l >> r >> c;
        v[l][r] = min(v[l][r], c);
    }
    V<V<int>> dp(n+1, V<int>(n+1, INF));
    dp[0][0] = 0;
    for(int r = 1; r <= n; r++){
        loop(i, r) dp[i][r] = dp[i][r-1];
        for(int l = 1; l <= r; l++){
            if(v[l][r] == INF) continue;
            for(int id = l-1; id < r; id++)
                for(int qtd = id+1-l; qtd <= id; qtd++)
                    dp[qtd+r-id][r] = min(dp[qtd+r-id][r], dp[qtd][id]+v[l][r]);
        }
        /*cout << "\n" << r << ":\n";
        for(auto u : dp){
            for(auto uu : u){
                if(uu == INF) cout << "X ";
                else cout << uu << " ";
            }
            cout << "\n";
        }
        cout << "\n";*/
    }
    int ans = INF;
    for(int id = k; id <= n; id++)
        for(int qtd = k; qtd <= id; qtd++)
            ans = min(ans, dp[qtd][id]);
    if(ans == INF) cout << "-1\n";
    else cout << ans << "\n";
}